//编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。 
//
// 示例： 
//
// 
//输入：25
//输出：9
//解释：(2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次) 
//
// 提示： 
//
// 
// n <= 10^9 
// 
//
// Related Topics 递归 数学 动态规划 👍 87 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2025-09-14 00:46:23
 * @description 面试题 17.06.2出现的次数
 */
public class NumberOf2sInRangeLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 NumberOf2sInRangeLcci fun=new NumberOf2sInRangeLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {


	char s[];
	int dp[][];

	public int numberOf2sInRange(int n) {
		s = Integer.toString(n).toCharArray();
		var m = s.length;
		dp = new int[m][m];
		for (var i = 0; i < m; i++) Arrays.fill(dp[i], -1);
		return f(0, 0, true);
	}
	/*
	i: 当前处理到第几位（从 0 开始）
	cnt2: 前 i 位中已经出现的数字 2 的个数
	isLimit: 当前是否受到 n 的约束
	函数返回：从第 i 位开始，在给定条件下能构造出的所有数字中数字 2 的总个数。
	isLimit: 如果为 true，表示前面填的数字都和 n 对应位上的数字相同，那么当前位填的数字不能超过 s[i]；如果为 false，当前位可以填 0-9 的任意数字。
	cnt2: 记录已经填入的数字 2 的个数，用于最终统计。
	使用 dp[i][cnt2] 来缓存结果，但只在不受约束时 (!isLimit) 才缓存，因为受约束的状态每个只会出现一次。
	对于每一位：
	确定当前位可以填的数字范围：如果受约束，范围为 0 到 s[i]；否则为 0 到 9
	枚举所有可能的数字 d
	递归处理下一位，更新 cnt2（如果 d == 2 则加 1）
	累加所有可能的结果
	当处理完所有位 (i == s.length) 时，返回当前累计的 cnt2
	* */
	int f(int i, int cnt2, boolean isLimit) {
		//到终点返回
		if (i == s.length) return cnt2;
		// 如果不受限制，且记忆过了，直接返回
		if (!isLimit && dp[i][cnt2] >= 0) return dp[i][cnt2];
		var res = 0;
		// 范围是。如果受约束0~s[i]，否则0~9
		for (int d = 0, up = isLimit ? s[i] - '0' : 9; d <= up; ++d) // 枚举要填入的数字 d
			//如果当前受约束但是没到顶，下一个不受，当前不受，则下一位也不受
			res += f(i + 1, cnt2 + (d == 2 ? 1 : 0), isLimit && d == up);
		// 如果不受约束的，记录一下（因为受约束的只出现一次）
		if (!isLimit) dp[i][cnt2] = res;
		return res;
	}

	/*
	*
	*
	* 问题分析：我们需要统计所有从0到n的数字中，数字2出现的总次数。例如，n=25时，2出现在数字2,12,20,21,22,23,24,25中，其中22出现两次，总次数为9。
关键观察：对于数字n，可以将其拆分为各位数字，然后逐位处理。对于每一位，考虑当前位的值，以及低位和高位的可能取值，来计算2出现的次数。
算法选择：使用数位DP。将数字n转换为字符串以便逐位处理。定义递归函数dp(pos, tight, count)，其中：
pos表示当前处理的位置（从高位到低位）。
tight表示之前的位是否紧密匹配n的相应位（即是否受到n的限制）。
count表示到当前位为止已经出现的2的次数。
记忆化：使用记忆化存储来避免重复计算，提高效率。
复杂度分析：时间复杂度为O(log n)，空间复杂度为O(log n)，因为数字n的位数是log10(n)。*/
		 public int numberOf2sInRange1(int n) {
			 // 递归 转换成数位
			 char[] digits = String.valueOf(n).toCharArray();
			 int len = digits.length;
			 // 多一个位置，代表当前是否受限制
			 Integer[][][] memo = new Integer[len][2][len * 2];
			 return dp(0, 1, 0, digits, memo);
		 }

		 private int dp(int pos, int tight, int count, char[] digits, Integer[][][] memo) {
			 // 到末尾 返回
			 if (pos == digits.length) {
				 return count;
			 }
			 // 记忆化
			 if (memo[pos][tight][count] != null) {
				 return memo[pos][tight][count];
			 }
			 // 计算当前的上限
			 int limit = tight == 1 ? digits[pos] - '0' : 9;
			 int total = 0;
			 // 枚举所有可能
			 for (int d = 0; d <= limit; d++) {
				 // 如果当前位受到限制，且当前位已经超过限制，则下一个位置也会受限
				 int newTight = (tight == 1 && d == limit) ? 1 : 0;
				 // 更新count
				 int newCount = count;
				// 如果当前位是2，则count加1
				 if (d == 2) {
					 newCount++;
				 }
				 // 递归处理下一位
				 total += dp(pos + 1, newTight, newCount, digits, memo);
			 }
			 // 返回结果
			 memo[pos][tight][count] = total;
			 return total;
		 }

	// 2
	// 12
	//22
	//20~29
	//32
	//42
	// 52 62 72 82 92
	// 102
	//112
	//122
	//120-129
	// 132 ~192
	// <10 1,<100 10+10=20,<1000 10*20+100=300,<10000 300*10*1000
	public int numberOf2sInRange2(int n) {
		if (n < 2) return 0;
		if (n < 12) return 1;

		String s = String.valueOf(n);
		int len = s.length();

		// dp[i] 表示 i+1 位数中2出现的总次数
		int[] dp = new int[len];
		dp[0] = 1; // 个位数

		// 计算dp数组
		for (int i = 1; i < len; i++) {
			dp[i] = 10 * dp[i - 1] + (int)Math.pow(10, i);
		}

		int result = 0;
		// 从高位到低位处理
		for (int i = 0; i < len; i++) {
			int digit = s.charAt(i) - '0';
			int remainingDigits = len - i - 1;
			int base = (int)Math.pow(10, remainingDigits);

			if (digit > 2) {
				result += base + digit * (remainingDigits > 0 ? dp[remainingDigits - 1] : 0);
			} else if (digit == 2) {
				// 处理剩余部分
				int remainingValue = 0;
				if (i < len - 1) {
					remainingValue = Integer.parseInt(s.substring(i + 1)) + 1;
				} else {
					remainingValue = 1;
				}
				result += remainingValue + digit * (remainingDigits > 0 ? dp[remainingDigits - 1] : 0);
			} else {
				result += digit * (remainingDigits > 0 ? dp[remainingDigits - 1] : 0);
			}
		}

		return result;
	}
	public int numberOf2sInRange3(int n) {
		int digit=(int)Math.log10(n)+1;
		int[] dp=new int[digit+1];
		dp[0]=0;
		int copy=n;
		int index=1;
		int res=0;
		//从低位到高位
		while(n>0){
			int k=n%10;
			// 等于2，贡献等于k*dp[idx-1]+余数，余数等于 整个数%10^(idx-1)，一共有0~模数个数，所以要+1，整个2开头的区间不完整所以要%
			if(k==2){
				res+=2*dp[index-1]+copy%(int)Math.pow(10,index-1)+1;
			}else if(k>2){
				// 大于2，贡献等于k*dp[idx-1]+10^(idx-1)，
				res+=k*dp[index-1]+(int)Math.pow(10,index-1);
			}else{
				// 小于2，贡献等于k*dp[idx-1]
				res+=k*dp[index-1];
			}
			dp[index]=10*dp[index-1]+(int)Math.pow(10,index-1);
			index++;
			n/=10;
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
